Thực đơn
Độ phức tạp thuật toán Bậc O-lớnGọi n {\displaystyle n} là độ lớn đầu vào. Tùy thuộc từng bài toán mà n {\displaystyle n} có thể nhận những giá trị khác nhau. Chẳng hạn, bài toán tính giai thừa thì n {\displaystyle n} chính là số cần tính giai thừa. Nhiều bài toán số trị, chẳng hạn tính sai phân thì n {\displaystyle n} là số chữ số có nghĩa cần đạt được. Trong các phép tính đối với ma trận thì n {\displaystyle n} là số hàng hoặc cột của ma trận.
Độ phức tạp của bài toán phụ thuộc vào n {\displaystyle n} . Ở đây ta không chỉ đặc trưng độ phức tạp bởi số lượng phép tính, mà dùng một đại lượng tổng quát là tài nguyên cần dùng R ( n ) {\displaystyle R(n)} . Đó có thể là số lượng phép tính (có thể tính cả số lần truy nhập bộ nhớ, hoặc ghi vào bộ nhớ); nhưng cũng có thể là thời gian thực hiện chương trình (độ phức tạp về thời gian) hoặc dung lượng bộ nhớ cần phải cấp để chạy chương trình (độ phức tạp về không gian).
Xét quan hệ giữa tài nguyên và độ lớn đầu vào, nếu như tìm được hằng số C > 0 {\displaystyle C>0} , C {\displaystyle C} không phụ thuộc vào n {\displaystyle n} , sao cho với n {\displaystyle n} đủ lớn, các hàm R ( n ) , g ( n ) {\displaystyle R(n),g(n)} đều dương và
R ( n ) ≤ C . g ( n ) {\displaystyle R(n)\leq C.g(n)}thì ta nói thuật toán có độ phức tạp cỡ O ( g ( n ) ) {\displaystyle O(g(n))} .
Độ phức tạp không phải là độ đo chính xác lượng tài nguyên máy cần dùng, mà đặc trưng cho động thái của hệ thống khi kích thước đầu vào tăng lên. Chẳng hạn với thuật toán có độ phức tạp tuyến tính O ( n ) {\displaystyle O(n)} (xem phần dưới), nếu kích thước đầu vào tăng gấp đôi thì có thể ước tính rằng tài nguyên cần dùng cũng tăng khoảng gấp đôi. Nhưng với thuật toán có độ phức tạp bình phương O ( n 2 ) {\displaystyle O(n^{2})} thì tài nguyên sẽ tăng gấp bốn. Mặt khác, với thuật toán có độ phức tạp hàm mũ O ( 2 n ) {\displaystyle O(2^{n})} thì chỉ cần công thêm 2 đơn vị vào độ lớn đầu vào cũng đã làm tài nguyên tăng gấp 4 lần (tức là theo cấp số nhân) rồi.
Các độ phức tạp thường gặp đối với các thuật toán thông thường gồm có:
Định nghĩa trên mang tính "an toàn" theo nghĩa nó chỉ xét sự tiêu tốn tài nguyên không vượt quá một ngưỡng g ( n ) {\displaystyle g(n)} nào đó, chứ không nhất thiết đúng bằng g ( n ) {\displaystyle g(n)} (chú ý dấu bất đẳng thức). Theo đó, một thuật toán có độ phức tạp cỡ n {\displaystyle n} thì đồng thời sẽ có độ phức tạp cỡ n 2 {\displaystyle n^{2}} ; với hàm ý rằng thuật toán này không bao giờ có động thái phức tạp hóa vượt qua ngưỡng đa thức bậc hai.
Thực đơn
Độ phức tạp thuật toán Bậc O-lớnLiên quan
Độ Động vật Động vật Chân khớp Đội tuyển bóng đá quốc gia Việt Nam Đội tuyển bóng đá U-23 quốc gia Việt Nam Động vật có dây sống Động đất Đội tuyển bóng đá U-23 quốc gia Hàn Quốc Đội tuyển bóng đá quốc gia Anh Đội Thiếu niên Tiền phong Hồ Chí MinhTài liệu tham khảo
WikiPedia: Độ phức tạp thuật toán https://commons.wikimedia.org/wiki/Category:Comput...